//Given the root of a binary search tree, and an integer k, return the kth (1-in
//dexed) smallest element in the tree. 
//
// 
// Example 1: 
//
// 
//Input: root = [3,1,4,null,2], k = 1
//Output: 1
// 
//
// Example 2: 
//
// 
//Input: root = [5,3,6,2,4,null,null,1], k = 3
//Output: 3
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is n. 
// 1 <= k <= n <= 104 
// 0 <= Node.val <= 104 
// 
//
// 
//Follow up: If the BST is modified often (i.e., we can do insert and delete ope
//rations) and you need to find the kth smallest frequently, how would you optimiz
//e? Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 452 👎 0


package leetcode.editor.cn;

//Java：Kth Smallest Element in a BST
class P230KthSmallestElementInABst {
    public static void main(String[] args) {
        Solution solution = new P230KthSmallestElementInABst().new Solution();
        // TO TEST
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(2);
        solution.kthSmallest(root, 1);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        int val = 0;
        int len = 0;

        public int kthSmallest(TreeNode root, int k) {
            len = k;
            kthSmallest(root);
            return val;
        }

        public void kthSmallest(TreeNode root) {

            if (root != null) {
                kthSmallest(root.left);
                len--;
                if (len == 0) {
                    val = root.val;
                    return;
                }
                kthSmallest(root.right);

            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
